#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;


class Solution {
public:
    long long distinctNames(vector<string>& ideas) {
        unordered_set<string> name[26];
        for (auto idea : ideas)
            name[idea[0] - 'a'].insert(idea.substr(1, idea.size() - 1));

        long long ans = 0;
        for (int a = 1; a < 26; ++a)
        {
            for (int b = 0; b < a; ++b)
            {
                int m = 0;
                for (auto& s : name[a])
                {
                    m += name[b].count(s);
                }
                ans += (name[a].size() - m) * (name[b].size() - m);
            }
        }
        return ans * 2;
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        if (n == 1) return nums[0];
        int a = nums[0], b = max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i)
        {
            int tmp = b;
            b = max(a + nums[i], b);
            a = tmp;
        }
        return b;
    }

    int deleteAndEarn(vector<int>& nums) {
        int maxVal = 0;
        for (int num : nums)
            maxVal = max(maxVal, num);
        vector<int> num(maxVal + 1);
        for (int val : nums)
            num[val] += val;
        return rob(num);
    }

    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        for (int i = 0; i < n + 2; ++i)  dp[0][i] = 0;;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        int ans = INT_MAX;
        for (int i = 1; i <= n; ++i)
            ans = min(dp[n][i], ans);
        return ans;
    }
};